package main

import (
	"fmt"
	. "local/algorithm/util"
)

/**
思考
通过DFS遍历BST，寻找其中规律:
每一个结点转换后的值等于本身的值加其右边所有节点值
这样如果我们如果通过右中左的方式遍历的话，右边所有节点的值其实是个累加值，记为sum,初始为0，遍历时只要让当前值root.Val = root.Val+sum，然后更新维护sum=root.Val即可
*/
func main() {
	a := GenerateTree([]int{2, 1, -1, -1, 3})
	output := convertBST(a)
	fmt.Println(output)
}

func convertBST(root *TreeNode) *TreeNode {
	sum := 0
	travel(root, &sum)
	return root
}

// 从大到小遍历 BST 并沿路更新 sum 和 节点值
func travel(root *TreeNode, sum *int) {
	if root == nil {
		return
	}
	travel(root.Right, sum)
	*sum += root.Val
	root.Val = *sum
	travel(root.Left, sum)
}
